1. Field of the Invention
The present invention relates to a key management method, an encryption system, and a sharing digital signature system which perform encryption and digital signature (authentication) as group operations by using an environment having a plurality of information processing apparatuses connected to each other through a communication line.
2. Related Background Art
An encryption technique is known as a technique of ensuring the prevention of the leakage of transmitted information to receiving apparatuses other than a designated apparatus (security of information) in an information communication system including a plurality of information processing apparatuses connected to each other through a communication line. The encryption technique is also known well as a technique which is effective at realizing an authentication function of checking whether received information has been transmitted from a designated apparatus or has not been tampered in the process of transmission, and a function called a digital signature which can prove to a third party that the received information has been transmitted from the designated apparatus, in addition to the above information security function.
An authentication and digital signature scheme using the RSA encryption algorithm as one of public-key encryption schemes is especially known widely (R. Rivest, A. Shamir, L. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystem", Communications of the ACM, 21, 2, 1978, pp. 120-126). The above authentication function is normally constituted by two procedures. In one procedure, signature is performed on the transmission side to give unique information to transmission information. In the other procedure, authentication is performed on the reception side to check, on the basis of the unique information from the transmission side which has been given to the information received by the reception side, whether the information has been transmitted from the designated apparatus and has not been tampered in the process of transmission.
A method of sharing the calculation of a digital signature for a given message among a plurality of information processing apparatuses connected to each other through a communication line in an information communication system in which security and authentication are realized in the above manner is disclosed in Yvo Desmedet, Yair Frankel ("Threshold cryptosystems", Advances in Cryptology-Crypto '89, 435, Springer-Verlag, 1990, pp. 307-315: "Shared Generation of Authenticators and Signatures", Advances in Cryptology-Crypto '91, 576, Springer-Verlag, 1992, pp. 457-469) (FIG. 7). The above plurality of information processing apparatuses will be referred to as a signatory group hereinafter, and each information processing apparatus joining the group will be referred to as a member. In addition, the number of members joining the group is represented by n.
Referring to FIG. 7, n pieces of partial information are generated from secret information (key) K. These pieces of information are secretly held by the n members. By synthesizing a predetermined number or more of pieces of information of K'i (i=1, 2, . . . , n) pieces of information held by these members, original secret information (key) K is restored, and a digital signature as a group signature can be generated. This scheme is called the sharing digital signature scheme. To generate a digital signature, secret information (key) unique to the signatory is required. Basically, the sharing digital signature scheme is a scheme of sharing secret information in an information communication system constituted by a plurality of members in the following manner.
A technique called secret sharing (SS) is used to share secret information. According to secret sharing, k pieces of partial information X.sub.1, X.sub.2, . . . , X.sub.k are generated from given secret information X. To restore the secret information X, t (t.ltoreq.k) or more pieces of partial information are required. With less than t-1 pieces of partial information, any information associated with the secret information cannot be obtained.
In this case, the number t of pieces of partial information required to restore the secret information is called a threshold. This scheme of sharing secret information is therefore called a threshold scheme. More specifically, the threshold scheme in A. Shamir ("How to Share a Secret", Communications of the ACM, Vol 22, 11, 1979) is realized in the following manner. To secretly share one piece of information among a plurality of pieces of partial information, a polynomial f(x) of the (t-1)th order having a constant term as the above secret information is randomly selected, and values f(i) (i=1, 2, . . . , k) of the polynomial are obtained with respect to the k different values. This value f(i) becomes the above partial value Xi. Although the secret information can be restored by polynomial interpolation using t pieces of partial information, any information associated with the secret information cannot be obtained with less than t-1 pieces of partial information.
That is, the sharing digital signature scheme using the RSA encryption algorithm based on the secret sharing scheme by Y. Desmedt and T. Frankel satisfies the following conditions:
1) The cooperation of t members is sufficient to generate a digital signature for a message given to a signatory group.
2) A digital signature for a given message cannot be generated with the number of members less than a threshold (t-1).
In above conventional sharing authentication system, when a signature is to be written as a group signature, all the members belonging to the group are handled equally. Under any condition, when a digital signature for a message given to a group is to be generated, the consensus of at least a predetermined number t of members is always required. For this reason, this system is not suited for a group having a hierarchical structure associated with a system of command or ranks.